﻿#include "SortAlgorithm.h"

// 工具函数
// 遍历数组
void PrintArray(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
// 交换元素
void Swap(int* arr, int i, int j)
{
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

// 插入类排序
// 插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}
// 希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

// 选择类排序
// 选择排序
void SelectSort(int* arr, int n)
{
	int start = 0;
	int end = n - 1;
	while (start < end)
	{
		int mini = start;
		int maxi = start;
		for (int i = start; i <= end; i++)
		{
			if (arr[i] < arr[mini]) mini = i;
			if (arr[i] > arr[maxi]) maxi = i;
		}

		Swap(arr, start, mini);
		if (maxi == start) maxi = mini;
		Swap(arr, end, maxi);

		start++;
		end--;
	}
}
// 堆排序 - 向下调整
void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] > arr[child])
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			Swap(arr, child, parent);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
// 堆排序
void HeapSort(int* arr, int n)
{
	// 建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
	// 堆排序逻辑
	int end = n - 1;
	while (end > 0)
	{
		Swap(arr, 0, end);
		AdjustDown(arr, end, 0);
		end--;
	}
}

// 交换类排序
// 冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int exchange = 0;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				exchange = 1;
				Swap(arr, j, j + 1);
			}
		}
		if (!exchange)
		{
			break;
		}
	}
}
// 快速排序 - Hoare法
int PartSortByHoare(int* arr, int start, int end)
{
	int key = arr[end];
	int keyIndex = end;
	while (start < end)
	{
		while (start < end && arr[start] <= key)
		{
			start++;
		}
		while (start < end && arr[end] >= key)
		{
			end--;
		}
		Swap(arr, start, end);
	}
	Swap(arr, start, keyIndex);
	return start;
}
// 快速排序 - 挖坑法
int PartSortByDigHole(int* arr, int start, int end)
{
	int key = arr[end];
	while (start < end)
	{
		while (start < end && arr[start] < key)
		{
			start++;
		}
		arr[end] = arr[start];
		while (start < end && arr[end] > key)
		{
			end--;
		}
		arr[start] = arr[end];
	}
	arr[start] = key;
	return start;
}
// 快速排序 - 前后指针法
int PartSortByTwoPointer(int* arr, int start, int end)
{
	int cur = start;
	int prev = start - 1;
	while (cur < end)
	{
		if (arr[cur] < arr[end])
		{
			Swap(arr, ++prev, cur);
		}
		cur++;
	}
	Swap(arr, ++prev, end);
	return prev;
}

// 快排递归实现
// 该排序共实现了Hoare法、挖坑法及前后指针法
// 修改PartSort方式，可切换不同实现
void QuickSortR(int* arr, int start, int end)
{
	if (start >= end) return;
	// 此处可替换单趟排序方式
	int mid = PartSortByTwoPointer(arr, start, end);
	QuickSortR(arr, start, mid - 1);
	QuickSortR(arr, mid + 1, end);
}

// 快排非递归实现
// 该排序共实现了Hoare法、挖坑法及前后指针法
// 修改PartSort方式，可切换不同实现
void QuickSortNonR(int* arr, int start, int end)
{
	if (start >= end) return;
	Stack stack;
	StackInit(&stack);
	StackPush(&stack, end);
	StackPush(&stack, start);

	while (!StackEmpty(&stack))
	{
		int begin = StackTop(&stack);
		StackPop(&stack);
		int end = StackTop(&stack);
		StackPop(&stack);

		// 此处可替换单趟排序方式
		int mid = PartSortByTwoPointer(arr, begin, end);
		
		if (begin < mid - 1)
		{
			StackPush(&stack, mid - 1);
			StackPush(&stack, begin);
		}
		if (mid + 1 < end)
		{
			StackPush(&stack, end);
			StackPush(&stack, mid + 1);
		}
	}
}

// 快速排序 - 总调用接口
// 可选择递归实现 / 非递归实现
void QuickSort(int* arr, int n)
{
	// QuickSortR(arr, 0, n - 1);
	QuickSortNonR(arr, 0, n - 1);
}

// 其他类排序

// 归并操作
void MergeArr(int* arr, int begin1, int end1, int begin2, int end2, int* tmp)
{
	int start = begin1;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}

	for (int i = start; i <= end2; i++)
	{
		arr[i] = tmp[i];
	}
}

// 归并递归实现
void MergeSortR(int* arr, int start, int end, int* tmp)
{
	if (start >= end) return;
	int mid = (start + end) / 2;
	MergeSortR(arr, start, mid, tmp);
	MergeSortR(arr, mid + 1, end, tmp);
	MergeArr(arr, start, mid, mid + 1, end, tmp);
}

// 归并非递归实现
void MergeSortNonR(int* arr, int start, int end, int* tmp)
{
	int gap = 1;
	while (gap < end - start + 1)
	{
		for (int i = 0; i <= end; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			if (begin2 > end)
			{
				break;
			}
			if (end2 > end)
			{
				end2 = end;
			}
			MergeArr(arr, begin1, end1, begin2, end2, tmp);
		}
		gap *= 2;
	}
}

// 其他类排序
// 归并排序
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	// MergeSortR(arr, 0, n - 1, tmp);
	MergeSortNonR(arr, 0, n - 1, tmp);
}
// 归并排序文件 - 外排序 / 磁盘排序
void MergeSortFile(const char* filename)
{
	// 将大文件拆分成排序好的小文件
	FILE* file = fopen(filename, "r");
	int* tmp = (int*)malloc(sizeof(int) * SIZE);

	char buffer[50];
	int num = 0;
	int index = 0;
	int fileIndex = 0;
	while (fscanf(file, "%d", &num) != EOF)
	{
		tmp[index++] = num;
		if(index == SIZE)
		{
			QuickSort(tmp, SIZE);
			sprintf(buffer, "sort/sort-%d.txt", fileIndex++);
			FILE* subfile = fopen(buffer, "w");
			for (int i = 0; i < SIZE; i++)
			{
				fprintf(subfile, "%d\n", tmp[i]);
			}
			fclose(subfile);
			index = 0;
		}
	}

	if (index != 0)
	{
		QuickSort(tmp, index);
		sprintf(buffer, "sort/sort-%d.txt", fileIndex++);
		FILE* subfile = fopen(buffer, "w");
		for (int i = 0; i < index; i++)
		{
			fprintf(subfile, "%d\n", tmp[i]);
		}
		fclose(subfile);
	}
	fclose(file);
	free(tmp);

	// 创建result.txt
	file = fopen("sort/result.txt", "w");
	fclose(file);

	// 小文件合并
	for (int i = 0; i < fileIndex; i++)
	{
		sprintf(buffer, "sort/sort-%d.txt", i);
		FILE* file1 = fopen("sort/result.txt", "r");
		FILE* file2 = fopen(buffer, "r");

		FILE* retFile = fopen("sort/tmp.txt", "w");

		int num1 = 0;
		int num2 = 0;
		int ret1 = fscanf(file1, "%d", &num1);
		int ret2 = fscanf(file2, "%d", &num2);

		while (ret1 != EOF && ret2 != EOF)
		{
			if (num1 <= num2)
			{
				fprintf(retFile, "%d\n", num1);
				ret1 = fscanf(file1, "%d", &num1);
			}
			else
			{
				fprintf(retFile, "%d\n", num2);
				ret2 = fscanf(file2, "%d", &num2);
			}
		}
		while (ret1 != EOF)
		{
			fprintf(retFile, "%d\n", num1);
			ret1 = fscanf(file1, "%d", &num1);
		}
		while (ret2 != EOF)
		{
			fprintf(retFile, "%d\n", num2);
			ret2 = fscanf(file2, "%d", &num2);
		}
		fclose(file1);
		fclose(file2);
		fclose(retFile);
		remove("sort/result.txt");
		remove(buffer);
		rename("sort/tmp.txt", "sort/result.txt");
	}
}
// 计数排序
void CountSort(int* arr, int n)
{
	int max = arr[0];
	int min = arr[0];
	for (int i = 1; i < n; i++)
	{
		if (arr[i] < min) min = arr[i];
		if (arr[i] > max) max = arr[i];
	}

	int range = max - min + 1;

	int* count = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range);
	for (int i = 0; i < n; i++) 
	{
		count[arr[i] - min]++;
	}

	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[index++] = min + i;
		}
	}
}